package 二分查找.easy;

/**
 * 1. 问题描述
 *   给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。
 *   请你统计并返回 grid 中 负数 的数目。
 *
 * 2. 算法分析
 *      1. 暴力扫描即可 时间复杂度为O(n^2)
 *
 *      2.
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 统计有序矩阵中的负数 {
    public static void main(String[] args) {
        System.out.println(test(new int[]{3,2,1,1,1,0,-1,-1,-1}));
    }


    /**
     * 暴力法  此方法完全没有利用有序矩阵的特点  时间复杂度为O(n^2)   不推荐
     * @param grid
     * @return
     */
    public static int countNegatives1(int[][] grid) {
        int ans  = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] < 0) {ans++;}
            }
        }
        return ans;
    }

    /**
     * 对上述暴力法的优化，本质上还是暴力法
     * @param grid
     * @return
     */
    public static int countNegatives2(int[][] grid) {
        int ans  = 0;
        int rowLen = grid[0].length;
        int left = 0; int right = rowLen - 1;
        for(int i = 0; i < grid.length; i++) {
            if(grid[i][0] < 0) { // 说明当前行所有元素为负的 因为每行元素是非递减的
                ans += rowLen;
            } else {
                int index = rowLen - 1;
                while(grid[i][index] < 0) {
                    index--;
                }
                ans += (rowLen - index - 1);
            }
        }
        return ans;
    }

    /**
     * 二分法   时间复杂度为O(mlogn)  但是此二分法指利用了行的单调性，没有利用列的单调性
     * @param grid
     * @return
     */
    public static int countNegatives3(int[][] grid) {
        int ans = 0;
        for(int i = 0; i < grid.length; i++) {
            if(grid[i][grid[0].length-1] < 0) {
                int left = 0; int right = grid[0].length - 1;
                int pos = -1;
                while(left <= right) {
                    int mid = left + (right-left)/2;
                    if(grid[i][mid] < 0) {
                        pos = mid;
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                ans += (grid[0].length-pos);
            } else {
                ans += 0;
            }
        }
        return ans;
    }

    /**
     * arr为非递增数组，找到该数组中的最后一个非负数的位置，如果没有返回-1
     * 1 1 1 -1 -1    返回2
     * i = 0  j = 4  mid = 2
     * @param arr
     * @return
     */
    public static int test(int[] arr) { // 有逻辑问题
        if (arr[0] < 0) {return -1;}
        int i = 0; int j = arr.length - 1;
        int pos = -1;
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (arr[mid] < 0) {
                pos = mid;
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return pos;
    }

    /**
     * 采用分治算法   通过利用行和列的单调性   目前而言最优化的一种解法
     * @param grid
     * @return
     */
    public static int countNegatives4(int[][] grid) {

        return 0;
    }


}
